package com.zyf.swordRefersOffer;
/**
 * 根据百度百科的生命游戏,简称为生命,是英国数学家约翰·何顿·康威在1970年发明的细胞自动机
 * 给定一个包含 m × n 个格子的面板,每一个格子都可以看成是一个细胞.每个细胞具有一个初始状态
 * live(1) 即为活细胞,或 dead(0)即为死细胞.每个活细胞与其八个相邻位置(水平、垂直、对角线)
 * 的细胞都遵循以下四条生存定律 :
 * 
 * 		1.如果活细胞周围八个位置的活细胞数少于两个,则该位置活细胞死亡;
 * 		2.如果活细胞周围八个位置有两个或三个活细胞,则该位置活细胞仍然存活;
 * 		3.如果活细胞周围八个位置有超过三个活细胞,则该位置活细胞死亡;
 * 		4.如果死细胞周围正好有三个活细胞,则给位置死细胞复活
 * 
 * 根据当前状态,写一个函数来计算面板上细胞的下一个(一次更新后的)状态.下一个状态是通过将上述
 * 规则同时应用于当前状态下的每个细胞所形成的的,其中细胞的出生和死亡是同时发生的
 * 
 * 实例 :
 * 		输入[0,1,0]			输出[0,0,0]
 * 			[0,0,1]				[1,0,1]
 * 			[1,1,1]				[0,1,1]
 * 			[0,0,0]				[0,1,0]
 * 
 * 分析 :
 *   没想到什么好的方法,就是简单粗暴的循环遍历.由于推荐原地算法同时格子同时更新,因此我们采取以下处理 :
 *     ·如果判断这一次更新后,该细胞死亡,则令其值为2
 *     ·如果判断这一次更新后,该细胞复活,则令其值为-1
 *     ·判断周围活细胞个数的条件 board[i][j] > 0
 *     ·判断周围死细胞个数的条件 board[i][j] <= 0
 *     ·全部遍历判断死活后,最后,再次遍历,令 2 -> 0 , -1 -> 1 ,即生成新复活的活细胞和新死亡的死亡细胞
 * @author lenovo
 * @Date 2020年7月7日
 * @Time 上午8:23:07
 */
public class _01_gameOfLife {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] nums = { { 0, 1, 0 }, { 0, 0, 1 }, { 1, 1, 1 }, { 0, 0, 0 } };
		gameOfLife(nums);
		for (int[] i : nums) {
			for (int i1 : i) {
				System.out.print(i1 + " ");
			}
			System.out.println();
		}
	}

	public static void gameOfLife(int[][] board) {
		if (board.length <= 0) {
			return;
		}
		for (int i = 0; i < board.length; i++) {
			// 遍历判断死活
			for (int j = 0; j < board[0].length; j++) {
				liveOrDie(board, i, j);
			}
		}
		// 对新复活或者死亡的细胞,恢复其 1/0 值
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {
				if (board[i][j] == -1) {
					board[i][j] = 1;
				} else if (board[i][j] == 2) {
					board[i][j] = 0;
				}
			}
		}
	}

	private static void liveOrDie(int[][] board, int cenX, int cenY) {
		// TODO Auto-generated method stub
		int alive = 0;// 周围活细胞个数
		@SuppressWarnings("unused")
		int dead = 0;// 周围死细胞个数
		for (int i = cenX - 1; i <= cenX + 1; i++) {
			// 遍历3×3的正方形细胞
			for (int j = cenY - 1; j <= cenY + 1; j++) {
				// 排除越界以及本身
				if ((i == cenX && j == cenY) || (i < 0 || i >= board.length) || (j < 0 || j >= board[0].length)) {
					continue;
				}
				// 后面用 -1 表示这一轮新复活的,为了不影响其他细胞的判断
				if (board[i][j] <= 0) {
					dead++;
				} else {
					// 同理,用2表示这一轮新死亡的
					alive++;
				}
			}
		}
		// 死细胞是否复活
		if (board[cenX][cenY] == 0) {
			if (alive == 3) {
				// -1 新复活的 board[cenX][cenY] = -1;
				board[cenX][cenY] = -1;
			}
		} else {
			// 活细胞是否死亡
			if (alive < 2 || alive > 3) {
				// 2 新死亡的
				board[cenX][cenY] = 2;
			}
		}
	}
}
